/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
    let i = 0, j = 0;
    while (i < s.length && j < s.length) {
        if (s[i] === t[j]) i++;
        j++;
    }
    return i === s.length;
};


var isSubsequence = function (s, t) {
    let m = s.length, n = t.length;
    let index = new Array(256);
    // 先记下 t 中每个字符出现的位置
    for (let i = 0; i < n; i++) {
        let c = t[i];
        if (index[c] == null) {
            index[c] = [];
        }
        index[c].push(i)
    }

    // 串t上的指针
    let j = 0;
    // 借助index查找s[i]
    for (let i = 0; i < m; i++) {
        let c = s[i];
        // 整个t压根没有字符c
        if (index[c] == null) return false
        let pos = left_bound(index[c], j);
        // 二分搜索区间中没有找到字符c
        if (pos == index[c].length) return false;

        // 向前移动指针j
        j = index[c][pos] + 1;
    }
    return true;
};

var left_bound = function (arr, tar) {
    let lo = 0, hi = arr.length;
    while (lo < hi) {

        let mid = lo + Math.floor((hi - lo) / 2);
        if (tar > arr[mid]) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}


console.log(isSubsequence("abc", "cacbhsdasc"))